class BinHeap:
    def __init__(self):
        self.heapList= [0]
        self.currentSize = 0

    def insert(self, k):
        # 添加到队列的末尾
        self.heapList.append(k)
        self.currentSize += 1

        # 为了保持堆次序, 新key上浮
        self._perUp(self.currentSize)

    def _perUp(self, i):
        while i // 2 > 0:
            # 新key的值比其父节点值小, 就需要交换
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2

    def delMin(self):
        # 总是取队首的元素
        retVal = self.heapList[1]

        # 用最后一个元素填充队首, 先不考虑堆序
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize -= 1

        # 最后一个已经移动到队首了, 所以删除
        self.heapList.pop()

        # 整理堆序, 新顶下沉
        self._percDown(1)
        return retVal

    def _percDown(self, i):
        while (i*2) <= self.currentSize:
            mc = self._minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc

    def _minChild(self, i):
        if i*2 + 1 > self.currentSize:
            # 只有一个子节点
            return 2*i
        else:
            # 左右子节点都存在, 比较大小, 返回小者
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i*2
            else:
                return i*2 + 1

    def buildHeap(self, alist):
        # 构建堆: 使用下沉法
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        print(len(self.heapList), i)
        
        while(i>0):
            print(self.heapList, i)
            self._percDown(i)
            i -= 1
        print(self.heapList, i)


if __name__ == '__main__':
    alist=[9,1,4,77,101]
    bh=BinHeap()
    bh.buildHeap(alist)
    print(bh.delMin())
    print(bh.delMin())